package io.github.hadyang.leetcode.offer;

import org.junit.Test;

/** @author haoyang.shi */
public class PatternMatch {

  @Test
  public void test() {
    System.out.println(match("aaa".toCharArray(), "a*a".toCharArray()));
    System.out.println(match("aaa".toCharArray(), "ab*ac*a".toCharArray()));
    System.out.println(match("aaa".toCharArray(), "aa.a".toCharArray()));
    System.out.println(match("aaa".toCharArray(), "ab*a".toCharArray()));
    System.out.println(match("".toCharArray(), ".*".toCharArray()));
    System.out.println(match("a".toCharArray(), "ab*".toCharArray()));
  }

  public boolean match(char[] str, char[] pattern) {
    if (str.length == 0 && new String(pattern).replaceAll(".\\*", "").length() == 0) {
      return true;
    }

    return match(str, 0, pattern, 0);
  }

  private boolean match(char[] str, int i, char[] pattern, int j) {
    if (i == str.length && j == pattern.length) {
      return true;
    }

    if (j >= pattern.length) return false;

    if (j + 1 < pattern.length && pattern[j + 1] == '*') {
      if ((i < str.length && pattern[j] == str[i]) || (pattern[j] == '.' && i != str.length)) {
        return match(str, i + 1, pattern, j + 2)
            || match(str, i + 1, pattern, j)
            || match(str, i, pattern, j + 2);
      } else {
        return match(str, i, pattern, j + 2);
      }
    }

    if ((i < str.length && pattern[j] == str[i]) || (pattern[j] == '.' && i != str.length)) {
      return match(str, i + 1, pattern, j + 1);
    }

    return false;
  }
}
